# https://www.bilibili.com/video/BV1T5411i7Gg/?spm_id_from=333.1365.list.card_archive.click&vd_source=ad559e41b561d48861f70d0187e51e02
# 21:50

from utils.log import Log
from utils.generator import Generator
from utils.bit_op import BitOp


# 尼姆博弈(Nim Game)
# 一共有n堆石头，两人轮流进行游戏
# 在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量谁先拿走最后的石头就获胜，返回最终谁会获胜
class Nim(Log):
    def __init__(self, arr):
        super(Nim, self).__init__()
        self.arr = [int(i) for i in arr]
        self._arr_xor = self.arr_xor()

    def arr_xor(self):
        arr_xor = 0
        for a in self.arr:
            arr_xor ^= a
        return arr_xor

    def who(self):
        return '先手' if self._arr_xor else '后手'

    def who_win(self):
        who = self.who()
        self.info(f"{self.__class__.__name__}(arr={self.arr}) {who}赢")
        # 先手的操作不能确定,貌似要考虑的情况有很多种
        # 尝试搞一下,不包对
        if who == '先手':
            for a in [i for i in self.arr if i >= self._arr_xor]:
                if a ^ self._arr_xor == a - self._arr_xor:
                    self.info(f"{a} 拿掉 {a ^ self._arr_xor ^ a}")
            for a in [i for i in self.arr if i < self._arr_xor]:
                if BitOp.left_most_1bit(a) == BitOp.left_most_1bit(self._arr_xor):
                    self.info(f"{a} 拿掉_ {a - (a ^ self._arr_xor)}")


# 反尼姆博弈(反常游戏)
# 一共有n堆石头，两人轮流进行游戏
# 在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量谁先拿走最后的石头就失败，返回最终谁会获胜
class AntiNim(Log):
    def __init__(self, arr):
        super(AntiNim, self).__init__()
        self.arr = [int(i) for i in arr]

    def who(self):
        eor = 0
        sum_one = 0
        for a in self.arr:
            eor ^= a
            sum_one += 1 if a == 1 else 0
        if sum_one == len(self.arr):
            return '先手' if BitOp.is_even(sum_one) else '后手'
        else:
            return '先手' if eor else '后手'

    def who_win(self):
        who = self.who()
        self.info(f"{self.__class__.__name__}(arr={self.arr}) {who}赢")


if __name__ == '__main__':
    Nim(Generator(count=5, min_val=1, max_val=10).do()).who_win()
    AntiNim([1, 1]).who_win()
    AntiNim([1, 1, 1]).who_win()
    AntiNim(Generator(count=3, min_val=1, max_val=5).do()).who_win()
